package tree.binarysearchtree;

import tree.TreeNode;

/**
 * @Classname : RecoverBinarySearchTree
 * @Description :
 * <a href="https://leetcode.cn/problems/recover-binary-search-tree/">99. 恢复二叉搜索树</a>
 * @Author : chentianyu
 * @Date 2023/1/13 21:55
 */


public class RecoverBinarySearchTree {
    private TreeNode mistake1;
    private TreeNode mistake2;
    private TreeNode pre;

    public void recoverTree(TreeNode root) {
        inorder(root);
        if (null != mistake1 && null != mistake2) {
            int temp = mistake1.val;
            mistake1.val = mistake2.val;
            mistake2.val = temp;
        }
    }

    private void inorder(TreeNode root) {
        if (null == root) return;

        inorder(root.left);

        if (null != pre && root.val < pre.val) {
            // 注意第一个节点是大的取pre，第二个节点是小的取当前root
            if (null == mistake1) mistake1 = pre;
            mistake2 = root;
        }
        pre = root;

        inorder(root.right);
    }
}
